import java.util.Stack;

/**
 * 堆的模拟实现
 */
public interface MyQueue<E> {
    //抽象方法
    public abstract boolean offer(E val);

    public abstract E poll();

    public abstract E peek();

    public abstract int size();

    public abstract boolean isEmpty();
}

//定义一个链表类
class MyLinkedList<E> implements MyQueue<E>{

    //定义节点类
    static class Node<E>{
        E val;
        Node next;

        public Node(E val){
            this.val = val;
        }
    }

    public MyLinkedList() {}

    //定义一个尾部节点
    private Node<E> last;
    @Override
    public boolean offer(E val) {
        //创建一个新的节点
        Node newNode = new Node(val);

        //如果创建失败，返回false
        if(newNode == null) return false;

        //首次入队列
       if(last == null){
           head = newNode;
           last = newNode;
       }//非首次入队列
        else{
            //1.将当前last的next修改尾newNode
           last.next = newNode;
           //2.将尾节点赋值为当前新创建的节点
           last = newNode;
       }
        return true;
    }

    //定义一个头节点
    private Node<E> head;
    @Override
    public E poll() {
       //如果没有元素不能执行出队列操作，因为此时的head为null,否则就抛异常
        if(head == null){
            //抛空引用异常
            throw new NullPointerException();
        }
        //先保存队列顶部元素的节点值
        E ret = head.val;
        //1.队列中只有一个元素
        if(head == last){
            head = null;
            last = null;
        }
        //2.将下一个节点引用赋值给头节点即可
        else{
            head = head.next;
        }
        return ret;
    }

    @Override
    public E peek() {
        //队列为空不能获取，抛异常
        if(head == null){
            throw new NullPointerException();
        }
        //返回队列顶部元素
        return head.val;
    }

    @Override
    public int size() {
        Node<E> tem = head;
        int size = 0;
        while(tem != null){
            size++;
            tem = tem.next;
        }
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    public static void main(String[] args) {
        MyQueue<Integer> myQueue = new MyLinkedList<>();
        //入对列
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);

        //获取元素个数
        int size = myQueue.size();
        System.out.println("myQueue中元素个数：" + size);

        //出队列
        myQueue.poll();
        myQueue.poll();

        //最后一个元素出队列:比较队列顶部元素是否与最后一个出队列元素相等
        System.out.println(myQueue.peek().equals(myQueue.peek()));

        //判断此时队列是否存在元素
        System.out.println(myQueue.isEmpty());
    }
}

class MyCircularQueue {

    Object[] objects;
    int size = 0;
    int front = 0;
    int rear = 0;
    public MyCircularQueue(int k) {
        objects = new Object[k + 1];
    }

    //入队列
    public boolean enQueue(int value) {

        if(isFull()){
            return false;
        }
        //保证下标合法
        rear = rear % objects.length;
        objects[rear++] = value;
        size++;
        return true;
    }

    //出队列
    public boolean deQueue() {
        if(isEmpty()) return false;
       //出队列后front + 1
        front = (front + 1) % objects.length;
        size--;
        return true;
    }

    public int Front() {
        if(isEmpty()) return -1;
        front = front % objects.length;
        return  (Integer) objects[front];
    }

    public int Rear() {
         if(isEmpty()) return -1;
         rear = rear % objects.length;
         if(rear -1 == -1){
             return (Integer)objects[objects.length -1];
         }
         return (Integer)objects[rear-1];
    }

    public boolean isEmpty() {
      return size == 0;
    }

    public boolean isFull() {
         return !isEmpty() && ((rear + 1) % objects.length == front);
    }
    //["MyCircularQueue","enQueue","Rear","Rear","deQueue","enQueue","Rear",
    // "deQueue","Front","deQueue","deQueue","deQueue"]
    //[[6],[6],[],[],[],[5],[],[],[],[],[],[]]
    public static void main(String[] args) {

        MyCircularQueue m = new MyCircularQueue(10);
    }
}

class Solution{

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    int size1 = 0;
    int size2 = 0;
    boolean f = false;
    public void offer(int node) {
        //入栈操作
        stack1.push(node);
        size1++;
    }

    public int poll() {
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push( stack1.pop());
                size1--;
                size2++;
            }
        }
        size2--;
        return stack2.pop();
    }

    public int peek(){
        //1.如果s2不为空
        if(!stack2.empty())
            return stack2.peek();
            //2.stack2为空，先将stack1中的元素出栈后加入stack2
            //返回stack2栈顶元素
        else{
            while(!stack1.empty()){
                stack2.push(stack1.pop());
                size1--;
                size2++;
            }
            return stack2.peek();
        }
    }

    public int size(){
        return size1 + size2;
    }

    public boolean isEmpty(){
        return size() == 0;
    }

    public static void main(String[] args) {
        Solution queue = new Solution();
        //入队列
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        //出队列【1，2】
        queue.poll();
        queue.poll();

        //入队列【4，5】
        queue.offer(4);
        queue.offer(5);

        //获取当前的个数
        System.out.println(queue.size());

        //出队列【3，4，5】
        queue.poll();
        queue.poll();
        queue.poll();

        //当前队列为空
        System.out.println(queue.isEmpty());

    }
}

